home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 12 - 1996 / 12.03 Mar 96 / SlidingTiles ƒ / TileMain.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-01-15  |  10.1 KB  |  393 lines  |  [TEXT/CWIE]
  1. /* 
  2.   Test code for the SlidingTiles Programmer's Challenge
  3. */
  4.  
  5. /* undef ANIMATE to delete animation of your solution */
  6. #define ANIMATE 1
  7. //#undef ANIMATE
  8.  
  9. /* define MOVE_USER_TILE to also move the user's tile in the MakeMove callback */
  10. #undef MOVE_USER_TILE
  11. //#define MOVE_USER_TILE
  12.  
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15. #include <string.h>
  16.  
  17. #include "Solve.h"
  18. #include "TileMain.h"
  19.  
  20. #define kNormalSize 20
  21. #define kOffset 20
  22. #define kMinWindowSize 300
  23. #define RECTWIDTH(r) ((r).right-(r).left)
  24. #define RECTHEIGHT(r) ((r).bottom-(r).top)
  25.  
  26. static long gNumRows,gNumCols;    /* initialized by test code */
  27. static long gEmptyRow,gEmptyCol;  /* initialized by test code */
  28. static long *gTiles;              /* initialized by test code */
  29.  
  30. static FontInfo gFontInfo;
  31. static WindowPtr gWind;
  32. static Rect gRect;
  33. static short gAnimateSpeed,gTileSize,gFontSize,gOffset;
  34.  
  35. #define TileValue(tiles,row,col,numCols) *(tiles+(row)*numCols+(col))
  36. #define OutOfRange(val,num)  (((val)<0) || ((val)>=(num)))
  37.  
  38. /*
  39.    Calculate the distance of the row/col tile from its correct position.
  40. */
  41. static long TileDist(long *tiles,long row,long col,long numCols) 
  42. { 
  43.   long row0,col0,val; 
  44.   val = TileValue(tiles,row,col,numCols); 
  45.   row0 = val / numCols; 
  46.   col0 = val - row0*numCols;
  47.   return abs(row-row0) + abs(col-col0); 
  48. }
  49.   
  50. /*
  51.    Calculate a score for this position, the sum of all tile distances
  52.    from their correct position.
  53. */
  54. static long CalcScore(long *tiles,long numRows,long numCols) 
  55. { 
  56.   long row,col,dist,cumDist=0;
  57.   for (row=0; row<numRows; ++row) {
  58.     for (col=0; col<numCols; ++col) {
  59.       if ((row==0) && (col==0)) continue;
  60.       dist = TileDist(tiles,row,col,numCols);
  61.       cumDist += dist;
  62.     }
  63.   }
  64.   return cumDist;
  65. }
  66.  
  67. /*
  68.    Draw a status string in the animation window.
  69. */
  70. static void MyDrawString(StringPtr str)
  71. {
  72.   Rect r;
  73.   
  74.   SetRect(&r,5,5,160,15);
  75.   EraseRect(&r);
  76.   MoveTo(r.left,r.bottom);
  77.   TextSize(9);
  78.   DrawString(str);
  79.   TextSize(gFontSize);
  80. }
  81.  
  82. /*
  83.    Draw the position score in the animation window.
  84. */
  85. static void DrawScore(long dist)
  86. {
  87.   Str255 str;
  88.   sprintf((char *)str,"Distance from solution: %ld",dist);
  89.   c2pstr((char *)str);
  90.   MyDrawString(str);
  91. }
  92.  
  93. /*
  94.    Draw one tile.
  95. */
  96. static void DrawOneTile(long *tiles,long theRow,long theCol)
  97. {
  98.   long val,wid;
  99.   Rect r;
  100.   Str255 valStr;
  101.   
  102.   SetRect(&r,gOffset,gOffset,gOffset+gTileSize,gOffset+gTileSize);
  103.   val = TileValue(tiles,theRow,theCol,gNumCols);
  104.   OffsetRect(&r,gTileSize*theCol,gTileSize*theRow);
  105.   if (val != 0) {
  106.     PenSize(2,2);
  107.     FrameRect(&r);
  108.     PenNormal();
  109.     NumToString(val,valStr);
  110.     InsetRect(&r, 1, 1);
  111.     EraseRect(&r);
  112.     wid = StringWidth(valStr);
  113.     MoveTo(gOffset + theCol*gTileSize+gTileSize/2-wid/2,gOffset + theRow*gTileSize+(gTileSize+gFontInfo.ascent)/2);
  114.     DrawString(valStr);
  115.   } else {
  116.     PaintRect(&r);
  117.   }
  118. }
  119.  
  120. /*
  121.    Draw all tiles
  122. */
  123. static void DrawTiles(WindowPtr wind)
  124. {
  125.   GrafPtr savePort;
  126.   long row,col;
  127.   Rect r;
  128.   GetPort(&savePort);
  129.   SetPort(wind);
  130.   EraseRect(&((GrafPtr)wind)->portRect);
  131.   SetRect(&r,gOffset-1,gOffset-1,gOffset+1+gNumCols*gTileSize,gOffset+1+gNumRows*gTileSize);
  132.   FrameRect(&r);
  133.   for (row=0; row<gNumRows; ++row) {
  134.     for (col=0; col<gNumCols; ++col) {
  135.       DrawOneTile(gTiles,row,col);
  136.     }
  137.   }
  138.   SetPort(savePort);
  139. }
  140.  
  141. /*
  142.    Initialize all tiles in their correct positions.  Allocate storage.
  143. */
  144. static long *InitTiles(long numRows, long numCols)
  145. {
  146. int row,col;
  147. long index = 0;
  148. long *gtiles = (long *)NewPtr(numRows*numCols*sizeof(long));
  149. long *tiles = gtiles;
  150.   if (nil != gtiles) {
  151.     for (row=0; row<numRows; ++row) {
  152.       for (col=0; col<numCols; ++col)
  153.         *tiles++ = index++;
  154.     }
  155.   }
  156.   return gtiles;
  157. }
  158.  
  159. /*
  160.    Dispose of tile storage.
  161. */
  162. static void DisposeTiles(long *tiles) 
  163. {
  164.   DisposePtr((Ptr)tiles);
  165. }
  166.  
  167. #define kMoveLeftRight 0x01
  168. #define kMoveUpLeft 0x02
  169.  
  170. #define Swap(tiles,a,b) \
  171. { long temp; \
  172.   temp=tiles[a];tiles[a]=tiles[b];tiles[b]=temp; \
  173. }
  174.  
  175. static void ExpressScramble(long *tiles,long numRows,long numCols) {
  176. //Scrambles a sliding tile puzzle of any size quickly.
  177. //(Courtesy of Ernst Munter)
  178. long i,b,numSwaps=0;
  179.   i=numRows*numCols;
  180.   do {
  181.     --i;
  182.     b=1+(rand()%i);
  183.     if (b!=i) {
  184.       Swap(tiles,i,b);
  185.       numSwaps++;
  186.     }
  187.   } while (i>3);
  188.   if (numSwaps&1) Swap(tiles,1,2);
  189.  
  190. //at this point the puzzle is scrambled, with every
  191. //possible legal (solvable) state reached with equal
  192. //probability, EXCEPT the blank tile is still at gTiles[0].
  193. //No unsolvable states can be reached with this algorithm.
  194.  
  195. //To move the blank tile inside the puzzle, use MakeMove
  196. //just a few times, say 1 or 2 times the number of tiles.
  197.  
  198. }
  199.  
  200. /*
  201.    Scramble the puzzle by moving the blank tile a bunch of times.
  202. */
  203. static void ScrambleTiles(long numIters, MoveProc Move)
  204. {
  205. long dir,i,rowToMove,colToMove;
  206. static long prevDir = -1;
  207. Boolean legal;
  208.   MoveTo(160,15);
  209.   DrawString("\p SCRAMBLING ...");
  210.   for (i=0; i<numIters; ++i) {
  211.     do {
  212.       rowToMove = gEmptyRow;
  213.       colToMove = gEmptyCol;
  214.       dir = Random()&0x03;
  215. /* dir ==  0x00                           move Up tile down into blank
  216.        ==  kMoveLeftRight                 move Left tile right into blank
  217.        ==  kMoveUpLeft                    move Down tile up into blank
  218.        ==  kMoveLeftRight+kMoveDownRight  move Right tile left into blank */
  219.       if (dir & kMoveLeftRight) /* move Left Or Right */ {
  220.         if (dir & kMoveUpLeft)  /* try to move tile left into empty square */ {
  221.           if (gEmptyCol < gNumCols-1)  ++colToMove;
  222.           else                         {dir ^= kMoveUpLeft; --colToMove;}
  223.         } else {                /* try to move tile right into empty square */
  224.           if (gEmptyCol > 0)           --colToMove;
  225.           else                         {dir ^= kMoveUpLeft; ++colToMove;}
  226.         }
  227.       } else {                  /* move Up or Down */
  228.         if (dir & kMoveUpLeft)  /* try to move tile up into empty square */ {
  229.           if (gEmptyRow < gNumRows-1)  ++rowToMove;
  230.           else                        {dir ^= kMoveUpLeft; --rowToMove;}
  231.         } else {                /* try to move tile down into empty square */
  232.           if (gEmptyRow > 0)           --rowToMove;
  233.           else                         {dir ^= kMoveUpLeft; ++rowToMove;}
  234.         }
  235.       }
  236.     } while ( (dir^prevDir) == kMoveUpLeft ); /* avoid sequential moves that cancel */
  237.     prevDir = dir;
  238.     legal = (*Move)(rowToMove,colToMove);
  239.     
  240.   }
  241. }
  242.  
  243. /*
  244.    Determine if the puzzle is in the pristine state.
  245. */
  246. static Boolean SolutionIsCorrect(long *tiles,long numRows,long numCols)
  247. {
  248.   long numTiles = numRows*numCols;
  249.   while (0 <= --numTiles)
  250.     if (numTiles != *(tiles+numTiles)) return false;
  251.   return true;
  252. }
  253.  
  254. /*
  255.    Update tile window.
  256. */
  257. void DoUpdate(WindowPtr wind)
  258. {
  259.   BeginUpdate(wind);
  260. #ifdef ANIMATE
  261.   DrawTiles(wind);
  262. #endif
  263.   EndUpdate(wind);
  264. }
  265.   
  266. /*
  267.    Callback routine to move tile.
  268. */
  269. static Boolean MakeMove(long tileToMoveRow,long tileToMoveCol) 
  270. {
  271.   long diff;
  272.   if (OutOfRange(tileToMoveRow,gNumRows)) return false;
  273.   if (OutOfRange(tileToMoveCol,gNumCols)) return false;
  274.   if (tileToMoveRow == gEmptyRow) {
  275.     diff = tileToMoveCol - gEmptyCol;
  276.   } else if (tileToMoveCol == gEmptyCol) {
  277.     diff = tileToMoveRow - gEmptyRow;
  278.   } else {
  279.     return false;
  280.   }
  281.   if ((diff != -1) && (diff != 1)) return false;
  282.   TileValue(gTiles,gEmptyRow,gEmptyCol,gNumCols) = 
  283.     TileValue(gTiles,tileToMoveRow,tileToMoveCol,gNumCols);
  284. #ifdef ANIMATE
  285.   if (gAnimateSpeed>0) {
  286.     DrawOneTile(gTiles,gEmptyRow,gEmptyCol);
  287.   }
  288. #endif
  289.   gEmptyRow = tileToMoveRow;
  290.   gEmptyCol = tileToMoveCol;
  291.   TileValue(gTiles,gEmptyRow,gEmptyCol,gNumCols) = 0;
  292. #ifdef ANIMATE
  293.   if (gAnimateSpeed>0) {
  294.     DrawOneTile(gTiles,gEmptyRow,gEmptyCol);
  295.     Delay(gAnimateSpeed,&diff);
  296.     DrawScore(CalcScore(gTiles,gNumRows,gNumCols));
  297.   }
  298. #endif
  299.   return true;
  300. }
  301.  
  302. /*
  303.    Execute one test case.
  304. */
  305. void RunOneCase(WindowPtr wind,long numRows,long numCols)
  306. {
  307.   GDHandle gd;
  308.   EventRecord ev;
  309.   long *userTiles;
  310.   short width,height,mBarHeight,hPos,vPos;
  311.   
  312. /* Initialize */
  313.   gWind = wind;
  314.   gNumRows = numRows;
  315.   gNumCols = numCols;
  316.   gEmptyRow = gEmptyCol = 0;
  317.   gTiles = InitTiles(gNumRows,gNumCols);
  318.   if (gTiles==nil) DebugStr("\p problem allocating tile memory");
  319.   gFontSize = 9;
  320.   if (numRows>numCols)   gTileSize = (kMinWindowSize-2*kOffset)/numRows;
  321.   else                   gTileSize = (kMinWindowSize-2*kOffset)/numCols;
  322.   gFontSize = gTileSize/2;
  323.   if (gTileSize<kNormalSize) {
  324.     gTileSize = kNormalSize;
  325.     gFontSize = 9;
  326.   }
  327.   TextSize(gFontSize);
  328.   GetFontInfo(&gFontInfo);
  329.   
  330. /* Adjust animation window size */
  331.   width = 2*kOffset + gTileSize*numCols;
  332.   height = 2*kOffset + gTileSize*numRows;
  333.   gOffset = kOffset;
  334.  
  335.   if (width<kMinWindowSize) {
  336.     width = kMinWindowSize;
  337.     gOffset = (kMinWindowSize - gTileSize*numCols)/2;
  338.   }
  339.   if (height<kMinWindowSize) {
  340.     height = kMinWindowSize;
  341.     gOffset = (kMinWindowSize - gTileSize*numRows)/2;
  342.   }
  343.   width = 2*gOffset + gTileSize*numCols;
  344.   height = 2*gOffset + gTileSize*numRows;
  345.   
  346. /* Adjust animation window position */
  347.   mBarHeight = LMGetMBarHeight();
  348.   gd = GetMainDevice();
  349.   gRect = (**gd).gdRect;
  350.   hPos = (RECTWIDTH(gRect)-width)/2;
  351.   vPos = mBarHeight+(RECTHEIGHT(gRect)-height-mBarHeight)/2;
  352.   if (hPos<0) hPos = 0;
  353.   if (vPos<mBarHeight) vPos=mBarHeight;
  354.   MoveWindow(gWind,hPos,vPos,false);
  355.   SizeWindow(gWind,width, height, true);
  356.   ShowWindow(gWind);
  357.   SetPort(gWind);
  358.  
  359. /* Initialize tiles */
  360.   gAnimateSpeed=0;
  361.   ExpressScramble(gTiles,numRows,numCols);
  362.   ScrambleTiles(numRows*numCols*40L,MakeMove);
  363.   DrawScore(CalcScore(gTiles,gNumRows,gNumCols));
  364.   DrawTiles(gWind);
  365.   gAnimateSpeed=4;
  366.  
  367.   userTiles = (long *)NewPtr(gNumRows*gNumCols*sizeof(long));
  368.   if (userTiles==nil) DebugStr("\p problem allocating user tile memory");
  369.   memcpy(userTiles,gTiles,gNumRows*gNumCols*sizeof(long));
  370.  
  371. /*
  372.   CALL USER SOLUTION
  373. */
  374.   SolveTiles(userTiles,gNumRows,gNumCols,MakeMove);
  375.  
  376.  
  377. /* Determine if solution is correct */
  378.   if (SolutionIsCorrect(gTiles,gNumRows,gNumCols)) {
  379.     MyDrawString("\p Solution is correct, hit a key to continue.");
  380.   } else {
  381.     MyDrawString("\p Solution is NOT correct, hit a key to continue.");
  382.   }
  383. /* Wait for acknowledgement */
  384.   SysBeep(1);
  385.   do { ;
  386.   } while (!WaitNextEvent(keyDownMask,&ev,0,nil));
  387.  
  388. /* Clean up and leave */
  389.   HideWindow(gWind);
  390.   DisposeTiles(userTiles);
  391.   DisposeTiles(gTiles);
  392. }
  393.